//比较含退格的字符串
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string q1 , q2;
        int maxlen = max(s.size(),t.size());
        for(size_t i = 0 ; i < maxlen ; ++i)
        {
            if(i < s.size())
            {
                if(s[i] == '#' && q1.size()) q1.pop_back();
                else if(s[i] != '#') q1 += s[i]; 
            }
            if(i < t.size())
            {
                if(t[i] == '#' && q2.size()) q2.pop_back();
                else if(t[i] != '#') q2 += t[i];
            }
        }

        return q1 == q2;
    }
};

//删除字符串中的所有相邻重复项
class Solution {
public:
    string removeDuplicates(string s) {
        string q;//栈
        for(size_t i = 0 ; i < s.size() ; ++i)
        {
            if(q.size() != 0 && q[q.size() - 1] == s[i]) q.pop_back();
            else q += s[i];
        }
        return q;
    }
};

//基本计算器Ⅱ
class Solution {
public:
    int calculate(string s) {
        char oper = '+';
        vector<int> st;
        for(size_t i = 0 ; i < s.size() ;)
        {
            //1、如果该数是数字，那么先提取出完整数字
            if(s[i] == ' ')
            {
                i++;
                continue;
            }
            
            if(s[i] >= '0' && s[i] <= '9')
            {
                //操作符是'+' or '-'，后面可能存在比它优先级更高的运算符
                //操作符是'*' or '/'，后面不存在比它优先级更高的运算符
                int temp = 0;
                while(isdigit(s[i]))
                {
                    temp *= 10;
                    temp += s[i]-'0';
                    ++i;
                }
                if(oper == '+')
                    st.push_back(temp);
                else if(oper == '-')
                    st.push_back(temp*(-1));
                else if(oper == '*')
                    st.back() *= temp;
                else if(oper == '/')
                    st.back() /= temp;

            }
            else 
            {
                //如果是运算符直接修改即可
                oper = s[i++];
            }
        }
        return accumulate(st.begin(),st.end(),0);
    }
};

//字符串解码
class Solution {
public:
    string decodeString(string s) {
        string st;
        for(size_t i = 0 ; i < s.size() ; ++i)
        {
            if(s[i] != ']') st.push_back(s[i]);
            else 
            {
                //依次取出字符串
                string temp;
                while (st.back() != '[')
                {
                    temp += st.back();
                    st.pop_back();
                }
                st.pop_back();//去掉'['
                int num = 0 , j = 0;
                while(st.size() != 0 &&st.back() >= '0' && st.back() <= '9')
                {
                    num += (st.back()-'0')*pow(10,j++);
                    st.pop_back();
                }
                reverse(temp.begin(),temp.end());
                while(num--)
                {
                    st += temp;
                }
            }
        }
        return st;
    }
};

//验证栈序列
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        vector<int> st;
        int popi = 0;
        for(size_t i = 0 ; i < pushed.size() ; ++i)
        {
            st.push_back(pushed[i]);
            while(!st.empty() && st.back() == popped[popi])
            {
                st.pop_back();
                popi++;
            }
        }
        return st.empty();
    }
};